package _interview100;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 */
public class No17 {
    public final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private List<String> ans;
    private StringBuilder path;
    private String digits;

    public List<String> letterCombinations(String digits) {
        this.ans = new ArrayList<>();
        this.path = new StringBuilder();
        this.digits = digits;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i == digits.length()) {
            if (!digits.isEmpty()) ans.add(path.toString());
            return;
        }
        String str = MAPPING[digits.charAt(i) - '0'];
        for (int j = 0; j < str.length(); j++) {
            path.append(str.charAt(j));
            dfs(i + 1);
            path.deleteCharAt(i);
        }
    }
}
